Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/unix/volume24/gnudiff1.15/part06

Internet Message Format | 1991-03-05 | 40.0 KB

Subject:  v24i021:  GNU Diff, version 1.15, Part06/08
Newsgroups: comp.sources.unix
Approved: [e-mail]
X-Checksum-Snefru: 20d4cb87 53dcbca3 10725bbd b18999e6

Submitted-by: Paul Eggert <[e-mail]>
Posting-number: Volume 24, Issue 21
Archive-name: gnudiff1.15/part06

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 6 (of 8)."
# Contents:  regex.c2
# Wrapped by eggert@ata on Mon Jan  7 11:25:31 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'regex.c2' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'regex.c2'\"
else
echo shar: Extracting \"'regex.c2'\" \(37881 characters\)
sed "s/^X//" >'regex.c2' <<'END_OF_FILE'
X
X
X
X/* Like re_search_2, below, but only one string is specified, and
X   doesn't let you say where to stop matching. */
X
Xint
Xre_search (pbufp, string, size, startpos, range, regs)
X     struct re_pattern_buffer *pbufp;
X     char *string;
X     int size, startpos, range;
X     struct re_registers *regs;
X{
X  return re_search_2 (pbufp, (char *) 0, 0, string, size, startpos, range,
X              regs, size);
X}
X
X
X/* Using the compiled pattern in PBUFP->buffer, first tries to match the
X   virtual concatenation of STRING1 and STRING2, starting first at index
X   STARTPOS, then at STARTPOS + 1, and so on.  RANGE is the number of
X   places to try before giving up.  If RANGE is negative, it searches
X   backwards, i.e., the starting positions tried are STARTPOS, STARTPOS
X   - 1, etc.  STRING1 and STRING2 are of SIZE1 and SIZE2, respectively.
X   In REGS, return the indices of the virtual concatenation of STRING1
X   and STRING2 that matched the entire PBUFP->buffer and its contained
X   subexpressions.  Do not consider matching one past the index MSTOP in
X   the virtual concatenation of STRING1 and STRING2.
X
X   The value returned is the position in the strings at which the match
X   was found, or -1 if no match was found, or -2 if error (such as
X   failure stack overflow).  */
X
Xint
Xre_search_2 (pbufp, string1, size1, string2, size2, startpos, range,
X         regs, mstop)
X     struct re_pattern_buffer *pbufp;
X     char *string1, *string2;
X     int size1, size2;
X     int startpos;
X     register int range;
X     struct re_registers *regs;
X     int mstop;
X{
X  register char *fastmap = pbufp->fastmap;
X  register unsigned char *translate = (unsigned char *) pbufp->translate;
X  int total_size = size1 + size2;
X  int endpos = startpos + range;
X  int val;
X
X  /* Check for out-of-range starting position.  */
X  if (startpos < 0  ||  startpos > total_size)
X    return -1;
X
X  /* Fix up range if it would eventually take startpos outside of the
X     virtual concatenation of string1 and string2.  */
X  if (endpos < -1)
X    range = -1 - startpos;
X  else if (endpos > total_size)
X    range = total_size - startpos;
X
X  /* Update the fastmap now if not correct already.  */
X  if (fastmap && !pbufp->fastmap_accurate)
X    re_compile_fastmap (pbufp);
X
X  /* If the search isn't to be a backwards one, don't waste time in a
X     long search for a pattern that says it is anchored.  */
X  if (pbufp->used > 0 && (enum regexpcode) pbufp->buffer[0] == begbuf
X      && range > 0)
X    {
X      if (startpos > 0)
X    return -1;
X      else
X    range = 1;
X    }
X
X  while (1)
X    {
X      /* If a fastmap is supplied, skip quickly over characters that
X         cannot possibly be the start of a match.  Note, however, that
X         if the pattern can possibly match the null string, we must
X         test it at each starting point so that we take the first null
X         string we get.  */
X
X      if (fastmap && startpos < total_size && pbufp->can_be_null != 1)
X    {
X      if (range > 0)    /* Searching forwards.  */
X        {
X          register int lim = 0;
X          register unsigned char *p;
X          int irange = range;
X          if (startpos < size1 && startpos + range >= size1)
X        lim = range - (size1 - startpos);
X
X          p = ((unsigned char *)
X           &(startpos >= size1 ? string2 - size1 : string1)[startpos]);
X
X              while (range > lim && !fastmap[translate
X                                             ? translate[*p++]
X                                             : *p++])
X            range--;
X          startpos += irange - range;
X        }
X      else                /* Searching backwards.  */
X        {
X          register unsigned char c;
X
X              if (string1 == 0 || startpos >= size1)
X        c = string2[startpos - size1];
X          else
X        c = string1[startpos];
X
X              c &= 0xff;
X          if (translate ? !fastmap[translate[c]] : !fastmap[c])
X        goto advance;
X        }
X    }
X
X      if (range >= 0 && startpos == total_size
X      && fastmap && pbufp->can_be_null == 0)
X    return -1;
X
X      val = re_match_2 (pbufp, string1, size1, string2, size2, startpos,
X            regs, mstop);
X      if (val >= 0)
X    return startpos;
X      if (val == -2)
X    return -2;
X
X#ifdef C_ALLOCA
X      alloca (0);
X#endif /* C_ALLOCA */
X
X    advance:
X      if (!range)
X        break;
X      else if (range > 0)
X        {
X          range--;
X          startpos++;
X        }
X      else
X        {
X          range++;
X          startpos--;
X        }
X    }
X  return -1;
X}
X
X
X
X#ifndef emacs   /* emacs never uses this.  */
Xint
Xre_match (pbufp, string, size, pos, regs)
X     struct re_pattern_buffer *pbufp;
X     char *string;
X     int size, pos;
X     struct re_registers *regs;
X{
X  return re_match_2 (pbufp, (char *) 0, 0, string, size, pos, regs, size);
X}
X#endif /* not emacs */
X
X
X/* The following are used for re_match_2, defined below:  */
X
X/* Roughly the maximum number of failure points on the stack.  Would be
X   exactly that if always pushed MAX_NUM_FAILURE_ITEMS each time we failed.  */
X
Xint re_max_failures = 2000;
X
X/* Routine used by re_match_2.  */
Xstatic int bcmp_translate ();
X
X
X/* Structure and accessing macros used in re_match_2:  */
X
Xstruct register_info
X{
X  unsigned is_active : 1;
X  unsigned matched_something : 1;
X};
X
X#define IS_ACTIVE(R)  ((R).is_active)
X#define MATCHED_SOMETHING(R)  ((R).matched_something)
X
X
X/* Macros used by re_match_2:  */
X
X
X/* I.e., regstart, regend, and reg_info.  */
X
X#define NUM_REG_ITEMS  3
X
X/* We push at most this many things on the stack whenever we
X   fail.  The `+ 2' refers to PATTERN_PLACE and STRING_PLACE, which are
X   arguments to the PUSH_FAILURE_POINT macro.  */
X
X#define MAX_NUM_FAILURE_ITEMS   (RE_NREGS * NUM_REG_ITEMS + 2)
X
X
X/* We push this many things on the stack whenever we fail.  */
X
X#define NUM_FAILURE_ITEMS  (last_used_reg * NUM_REG_ITEMS + 2)
X
X
X/* This pushes most of the information about the current state we will want
X   if we ever fail back to it.  */
X
X#define PUSH_FAILURE_POINT(pattern_place, string_place)            \
X  {                                    \
X    short last_used_reg, this_reg;                    \
X                                    \
X    /* Find out how many registers are active or have been matched.    \
X       (Aside from register zero, which is only set at the end.)  */    \
X    for (last_used_reg = RE_NREGS - 1; last_used_reg > 0; last_used_reg--)\
X      if (regstart[last_used_reg] != (unsigned char *) -1)        \
X        break;                                \
X                                    \
X    if (stacke - stackp < NUM_FAILURE_ITEMS)                \
X      {                                    \
X    unsigned char **stackx;                        \
X    if (stacke - stackb > re_max_failures * MAX_NUM_FAILURE_ITEMS)    \
X      return -2;                            \
X                                    \
X        /* Roughly double the size of the stack.  */            \
X        stackx = (unsigned char **) alloca (2 * MAX_NUM_FAILURE_ITEMS    \
X                            * (stacke - stackb)        \
X                                            * sizeof (unsigned char *));\
X    /* Only copy what is in use.  */                \
X        bcopy (stackb, stackx, (stackp - stackb) * sizeof (char *));    \
X    stackp = stackx + (stackp - stackb);                \
X    stackb = stackx;                        \
X    stacke = stackb + 2 * MAX_NUM_FAILURE_ITEMS * (stacke - stackb);\
X      }                                    \
X                                    \
X    /* Now push the info for each of those registers.  */        \
X    for (this_reg = 1; this_reg <= last_used_reg; this_reg++)        \
X      {                                    \
X        *stackp++ = regstart[this_reg];                    \
X        *stackp++ = regend[this_reg];                    \
X        *stackp++ = (unsigned char *) ®_info[this_reg];        \
X      }                                    \
X                                    \
X    /* Push how many registers we saved.  */                \
X    *stackp++ = (unsigned char *) last_used_reg;            \
X                                    \
X    *stackp++ = pattern_place;                                          \
X    *stackp++ = string_place;                                           \
X  }
X
X
X/* This pops what PUSH_FAILURE_POINT pushes.  */
X
X#define POP_FAILURE_POINT()                        \
X  {                                    \
X    int temp;                                \
X    stackp -= 2;        /* Remove failure points.  */        \
X    temp = (int) *--stackp;    /* How many regs pushed.  */            \
X    temp *= NUM_REG_ITEMS;    /* How much to take off the stack.  */    \
X    stackp -= temp;         /* Remove the register info.  */    \
X  }
X
X
X#define MATCHING_IN_FIRST_STRING  (dend == end_match_1)
X
X/* Is true if there is a first string and if PTR is pointing anywhere
X   inside it or just past the end.  */
X
X#define IS_IN_FIRST_STRING(ptr)                     \
X    (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
X
X/* Call before fetching a character with *d.  This switches over to
X   string2 if necessary.  */
X
X#define PREFETCH                            \
X while (d == dend)                                \
X  {                                    \
X    /* end of string2 => fail.  */                    \
X    if (dend == end_match_2)                         \
X      goto fail;                            \
X    /* end of string1 => advance to string2.  */             \
X    d = string2;                                \
X    dend = end_match_2;                            \
X  }
X
X
X/* Call this when have matched something; it sets `matched' flags for the
X   registers corresponding to the subexpressions of which we currently
X   are inside.  */
X#define SET_REGS_MATCHED                         \
X  { unsigned this_reg;                             \
X    for (this_reg = 0; this_reg < RE_NREGS; this_reg++)         \
X      {                                 \
X        if (IS_ACTIVE(reg_info[this_reg]))                \
X          MATCHED_SOMETHING(reg_info[this_reg]) = 1;            \
X        else                                \
X          MATCHED_SOMETHING(reg_info[this_reg]) = 0;            \
X      }                                 \
X  }
X
X/* Test if at very beginning or at very end of the virtual concatenation
X   of string1 and string2.  If there is only one string, we've put it in
X   string2.  */
X
X#define AT_STRINGS_BEG  (d == (size1 ? string1 : string2)  ||  !size2)
X#define AT_STRINGS_END  (d == end2)
X
X#define AT_WORD_BOUNDARY                        \
X  (AT_STRINGS_BEG || AT_STRINGS_END || IS_A_LETTER (d - 1) != IS_A_LETTER (d))
X
X/* We have two special cases to check for:
X     1) if we're past the end of string1, we have to look at the first
X        character in string2;
X     2) if we're before the beginning of string2, we have to look at the
X        last character in string1; we assume there is a string1, so use
X        this in conjunction with AT_STRINGS_BEG.  */
X#define IS_A_LETTER(d)                            \
X  (SYNTAX ((d) == end1 ? *string2 : (d) == string2 - 1 ? *(end1 - 1) : *(d))\
X   == Sword)
X
X
X/* Match the pattern described by PBUFP against the virtual
X   concatenation of STRING1 and STRING2, which are of SIZE1 and SIZE2,
X   respectively.  Start the match at index POS in the virtual
X   concatenation of STRING1 and STRING2.  In REGS, return the indices of
X   the virtual concatenation of STRING1 and STRING2 that matched the
X   entire PBUFP->buffer and its contained subexpressions.  Do not
X   consider matching one past the index MSTOP in the virtual
X   concatenation of STRING1 and STRING2.
X
X   If pbufp->fastmap is nonzero, then it had better be up to date.
X
X   The reason that the data to match are specified as two components
X   which are to be regarded as concatenated is so this function can be
X   used directly on the contents of an Emacs buffer.
X
X   -1 is returned if there is no match.  -2 is returned if there is an
X   error (such as match stack overflow).  Otherwise the value is the
X   length of the substring which was matched.  */
X
Xint
Xre_match_2 (pbufp, string1_arg, size1, string2_arg, size2, pos, regs, mstop)
X     struct re_pattern_buffer *pbufp;
X     char *string1_arg, *string2_arg;
X     int size1, size2;
X     int pos;
X     struct re_registers *regs;
X     int mstop;
X{
X  register unsigned char *p = (unsigned char *) pbufp->buffer;
X
X  /* Pointer to beyond end of buffer.  */
X  register unsigned char *pend = p + pbufp->used;
X
X  unsigned char *string1 = (unsigned char *) string1_arg;
X  unsigned char *string2 = (unsigned char *) string2_arg;
X  unsigned char *end1;        /* Just past end of first string.  */
X  unsigned char *end2;        /* Just past end of second string.  */
X
X  /* Pointers into string1 and string2, just past the last characters in
X     each to consider matching.  */
X  unsigned char *end_match_1, *end_match_2;
X
X  register unsigned char *d, *dend;
X  register int mcnt;            /* Multipurpose.  */
X  unsigned char *translate = (unsigned char *) pbufp->translate;
X  unsigned is_a_jump_n = 0;
X
X /* Failure point stack.  Each place that can handle a failure further
X    down the line pushes a failure point on this stack.  It consists of
X    restart, regend, and reg_info for all registers corresponding to the
X    subexpressions we're currently inside, plus the number of such
X    registers, and, finally, two char *'s.  The first char * is where to
X    resume scanning the pattern; the second one is where to resume
X    scanning the strings.  If the latter is zero, the failure point is a
X    ``dummy''; if a failure happens and the failure point is a dummy, it
X    gets discarded and the next next one is tried.  */
X
X  unsigned char *initial_stack[MAX_NUM_FAILURE_ITEMS * NFAILURES];
X  unsigned char **stackb = initial_stack;
X  unsigned char **stackp = stackb;
X  unsigned char **stacke = &stackb[MAX_NUM_FAILURE_ITEMS * NFAILURES];
X
X
X  /* Information on the contents of registers. These are pointers into
X     the input strings; they record just what was matched (on this
X     attempt) by a subexpression part of the pattern, that is, the
X     regnum-th regstart pointer points to where in the pattern we began
X     matching and the regnum-th regend points to right after where we
X     stopped matching the regnum-th subexpression.  (The zeroth register
X     keeps track of what the whole pattern matches.)  */
X
X  unsigned char *regstart[RE_NREGS];
X  unsigned char *regend[RE_NREGS];
X
X  /* The is_active field of reg_info helps us keep track of which (possibly
X     nested) subexpressions we are currently in. The matched_something
X     field of reg_info[reg_num] helps us tell whether or not we have
X     matched any of the pattern so far this time through the reg_num-th
X     subexpression.  These two fields get reset each time through any
X     loop their register is in.  */
X
X  struct register_info reg_info[RE_NREGS];
X
X
X  /* The following record the register info as found in the above
X     variables when we find a match better than any we've seen before.
X     This happens as we backtrack through the failure points, which in
X     turn happens only if we have not yet matched the entire string.  */
X
X  unsigned best_regs_set = 0;
X  unsigned char *best_regstart[RE_NREGS];
X  unsigned char *best_regend[RE_NREGS];
X
X
X  /* Initialize subexpression text positions to -1 to mark ones that no
X     \( or ( and \) or ) has been seen for. Also set all registers to
X     inactive and mark them as not having matched anything or ever
X     failed.  */
X  for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
X    {
X      regstart[mcnt] = regend[mcnt] = (unsigned char *) -1;
X      IS_ACTIVE (reg_info[mcnt]) = 0;
X      MATCHED_SOMETHING (reg_info[mcnt]) = 0;
X    }
X
X  if (regs)
X    for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
X      regs->start[mcnt] = regs->end[mcnt] = -1;
X
X  /* Set up pointers to ends of strings.
X     Don't allow the second string to be empty unless both are empty.  */
X  if (size2 == 0)
X    {
X      string2 = string1;
X      size2 = size1;
X      string1 = 0;
X      size1 = 0;
X    }
X  end1 = string1 + size1;
X  end2 = string2 + size2;
X
X  /* Compute where to stop matching, within the two strings.  */
X  if (mstop <= size1)
X    {
X      end_match_1 = string1 + mstop;
X      end_match_2 = string2;
X    }
X  else
X    {
X      end_match_1 = end1;
X      end_match_2 = string2 + mstop - size1;
X    }
X
X  /* `p' scans through the pattern as `d' scans through the data. `dend'
X     is the end of the input string that `d' points within. `d' is
X     advanced into the following input string whenever necessary, but
X     this happens before fetching; therefore, at the beginning of the
X     loop, `d' can be pointing at the end of a string, but it cannot
X     equal string2.  */
X
X  if (size1 != 0 && pos <= size1)
X    d = string1 + pos, dend = end_match_1;
X  else
X    d = string2 + pos - size1, dend = end_match_2;
X
X
X  /* This loops over pattern commands.  It exits by returning from the
X     function if match is complete, or it drops through if match fails
X     at this starting point in the input data.  */
X
X  while (1)
X    {
X      is_a_jump_n = 0;
X      /* End of pattern means we might have succeeded.  */
X      if (p == pend)
X    {
X      /* If not end of string, try backtracking.  Otherwise done.  */
X          if (d != end_match_2)
X        {
X              if (stackp != stackb)
X                {
X                  /* More failure points to try.  */
X
X                  unsigned in_same_string =
X                          IS_IN_FIRST_STRING (best_regend[0])
X                        == MATCHING_IN_FIRST_STRING;
X
X                  /* If exceeds best match so far, save it.  */
X                  if (! best_regs_set
X                      || (in_same_string && d > best_regend[0])
X                      || (! in_same_string && ! MATCHING_IN_FIRST_STRING))
X                    {
X                      best_regs_set = 1;
X                      best_regend[0] = d;    /* Never use regstart[0].  */
X
X                      for (mcnt = 1; mcnt < RE_NREGS; mcnt++)
X                        {
X                          best_regstart[mcnt] = regstart[mcnt];
X                          best_regend[mcnt] = regend[mcnt];
X                        }
X                    }
X                  goto fail;
X                }
X              /* If no failure points, don't restore garbage.  */
X              else if (best_regs_set)
X                {
X          restore_best_regs:
X                  /* Restore best match.  */
X                  d = best_regend[0];
X
X          for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
X            {
X              regstart[mcnt] = best_regstart[mcnt];
X              regend[mcnt] = best_regend[mcnt];
X            }
X                }
X            }
X
X      /* If caller wants register contents data back, convert it
X         to indices.  */
X      if (regs)
X        {
X          regs->start[0] = pos;
X          if (MATCHING_IN_FIRST_STRING)
X        regs->end[0] = d - string1;
X          else
X        regs->end[0] = d - string2 + size1;
X          for (mcnt = 1; mcnt < RE_NREGS; mcnt++)
X        {
X          if (regend[mcnt] == (unsigned char *) -1)
X            {
X              regs->start[mcnt] = -1;
X              regs->end[mcnt] = -1;
X              continue;
X            }
X          if (IS_IN_FIRST_STRING (regstart[mcnt]))
X            regs->start[mcnt] = regstart[mcnt] - string1;
X          else
X            regs->start[mcnt] = regstart[mcnt] - string2 + size1;
X
X          if (IS_IN_FIRST_STRING (regend[mcnt]))
X            regs->end[mcnt] = regend[mcnt] - string1;
X          else
X            regs->end[mcnt] = regend[mcnt] - string2 + size1;
X        }
X        }
X      return d - pos - (MATCHING_IN_FIRST_STRING
X                ? string1
X                : string2 - size1);
X        }
X
X      /* Otherwise match next pattern command.  */
X#ifdef SWITCH_ENUM_BUG
X      switch ((int) ((enum regexpcode) *p++))
X#else
X      switch ((enum regexpcode) *p++)
X#endif
X    {
X
X    /* \( [or `(', as appropriate] is represented by start_memory,
X           \) by stop_memory.  Both of those commands are followed by
X           a register number in the next byte.  The text matched
X           within the \( and \) is recorded under that number.  */
X    case start_memory:
X          regstart[*p] = d;
X          IS_ACTIVE (reg_info[*p]) = 1;
X          MATCHED_SOMETHING (reg_info[*p]) = 0;
X          p++;
X          break;
X
X    case stop_memory:
X          regend[*p] = d;
X          IS_ACTIVE (reg_info[*p]) = 0;
X
X          /* If just failed to match something this time around with a sub-
X         expression that's in a loop, try to force exit from the loop.  */
X          if ((! MATCHED_SOMETHING (reg_info[*p])
X           || (enum regexpcode) p[-3] == start_memory)
X          && (p + 1) != pend)
X            {
X          register unsigned char *p2 = p + 1;
X              mcnt = 0;
X              switch (*p2++)
X                {
X                  case jump_n:
X            is_a_jump_n = 1;
X                  case finalize_jump:
X          case maybe_finalize_jump:
X          case jump:
X          case dummy_failure_jump:
X                    EXTRACT_NUMBER_AND_INCR (mcnt, p2);
X            if (is_a_jump_n)
X              p2 += 2;
X                    break;
X                }
X          p2 += mcnt;
X
X              /* If the next operation is a jump backwards in the pattern
X             to an on_failure_jump, exit from the loop by forcing a
X                 failure after pushing on the stack the on_failure_jump's
X                 jump in the pattern, and d.  */
X          if (mcnt < 0 && (enum regexpcode) *p2++ == on_failure_jump)
X        {
X                  EXTRACT_NUMBER_AND_INCR (mcnt, p2);
X                  PUSH_FAILURE_POINT (p2 + mcnt, d);
X                  goto fail;
X                }
X            }
X          p++;
X          break;
X
X    /* \<digit> has been turned into a `duplicate' command which is
X           followed by the numeric value of <digit> as the register number.  */
X        case duplicate:
X      {
X        int regno = *p++;   /* Get which register to match against */
X        register unsigned char *d2, *dend2;
X
X        /* Where in input to try to start matching.  */
X            d2 = regstart[regno];
X
X            /* Where to stop matching; if both the place to start and
X               the place to stop matching are in the same string, then
X               set to the place to stop, otherwise, for now have to use
X               the end of the first string.  */
X
X            dend2 = ((IS_IN_FIRST_STRING (regstart[regno])
X              == IS_IN_FIRST_STRING (regend[regno]))
X             ? regend[regno] : end_match_1);
X        while (1)
X          {
X        /* If necessary, advance to next segment in register
X                   contents.  */
X        while (d2 == dend2)
X          {
X            if (dend2 == end_match_2) break;
X            if (dend2 == regend[regno]) break;
X            d2 = string2, dend2 = regend[regno];  /* end of string1 => advance to string2. */
X          }
X        /* At end of register contents => success */
X        if (d2 == dend2) break;
X
X        /* If necessary, advance to next segment in data.  */
X        PREFETCH;
X
X        /* How many characters left in this segment to match.  */
X        mcnt = dend - d;
X
X        /* Want how many consecutive characters we can match in
X                   one shot, so, if necessary, adjust the count.  */
X                if (mcnt > dend2 - d2)
X          mcnt = dend2 - d2;
X
X        /* Compare that many; failure if mismatch, else move
X                   past them.  */
X        if (translate
X                    ? bcmp_translate (d, d2, mcnt, translate)
X                    : bcmp (d, d2, mcnt))
X          goto fail;
X        d += mcnt, d2 += mcnt;
X          }
X      }
X      break;
X
X    case anychar:
X      PREFETCH;      /* Fetch a data character. */
X      /* Match anything but a newline, maybe even a null.  */
X      if ((translate ? translate[*d] : *d) == '\n'
X              || ((obscure_syntax & RE_DOT_NOT_NULL)
X                  && (translate ? translate[*d] : *d) == '\000'))
X        goto fail;
X      SET_REGS_MATCHED;
X          d++;
X      break;
X
X    case charset:
X    case charset_not:
X      {
X        int not = 0;        /* Nonzero for charset_not.  */
X        register int c;
X        if (*(p - 1) == (unsigned char) charset_not)
X          not = 1;
X
X        PREFETCH;        /* Fetch a data character. */
X
X        if (translate)
X          c = translate[*d];
X        else
X          c = *d;
X
X        if (c < *p * BYTEWIDTH
X        && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
X          not = !not;
X
X        p += 1 + *p;
X
X        if (!not) goto fail;
X        SET_REGS_MATCHED;
X            d++;
X        break;
X      }
X
X    case begline:
X          if ((size1 != 0 && d == string1)
X              || (size1 == 0 && size2 != 0 && d == string2)
X              || (d && d[-1] == '\n')
X              || (size1 == 0 && size2 == 0))
X            break;
X          else
X            goto fail;
X
X    case endline:
X      if (d == end2
X          || (d == end1 ? (size2 == 0 || *string2 == '\n') : *d == '\n'))
X        break;
X      goto fail;
X
X    /* `or' constructs are handled by starting each alternative with
X           an on_failure_jump that points to the start of the next
X           alternative.  Each alternative except the last ends with a
X           jump to the joining point.  (Actually, each jump except for
X           the last one really jumps to the following jump, because
X           tensioning the jumps is a hassle.)  */
X
X    /* The start of a stupid repeat has an on_failure_jump that points
X       past the end of the repeat text. This makes a failure point so
X           that on failure to match a repetition, matching restarts past
X           as many repetitions have been found with no way to fail and
X           look for another one.  */
X
X    /* A smart repeat is similar but loops back to the on_failure_jump
X       so that each repetition makes another failure point.  */
X
X    case on_failure_jump:
X        on_failure:
X          EXTRACT_NUMBER_AND_INCR (mcnt, p);
X          PUSH_FAILURE_POINT (p + mcnt, d);
X          break;
X
X    /* The end of a smart repeat has a maybe_finalize_jump back.
X       Change it either to a finalize_jump or an ordinary jump.  */
X    case maybe_finalize_jump:
X          EXTRACT_NUMBER_AND_INCR (mcnt, p);
X      {
X        register unsigned char *p2 = p;
X        /* Compare what follows with the beginning of the repeat.
X           If we can establish that there is nothing that they would
X           both match, we can change to finalize_jump.  */
X        while (p2 + 1 != pend
X           && (*p2 == (unsigned char) stop_memory
X               || *p2 == (unsigned char) start_memory))
X          p2 += 2;                /* Skip over reg number.  */
X        if (p2 == pend)
X          p[-3] = (unsigned char) finalize_jump;
X        else if (*p2 == (unsigned char) exactn
X             || *p2 == (unsigned char) endline)
X          {
X        register int c = *p2 == (unsigned char) endline ? '\n' : p2[2];
X        register unsigned char *p1 = p + mcnt;
X        /* p1[0] ... p1[2] are an on_failure_jump.
X           Examine what follows that.  */
X        if (p1[3] == (unsigned char) exactn && p1[5] != c)
X          p[-3] = (unsigned char) finalize_jump;
X        else if (p1[3] == (unsigned char) charset
X             || p1[3] == (unsigned char) charset_not)
X          {
X            int not = p1[3] == (unsigned char) charset_not;
X            if (c < p1[4] * BYTEWIDTH
X            && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
X              not = !not;
X            /* `not' is 1 if c would match.  */
X            /* That means it is not safe to finalize.  */
X            if (!not)
X              p[-3] = (unsigned char) finalize_jump;
X          }
X          }
X      }
X      p -= 2;        /* Point at relative address again.  */
X      if (p[-1] != (unsigned char) finalize_jump)
X        {
X          p[-1] = (unsigned char) jump;
X          goto nofinalize;
X        }
X        /* Note fall through.  */
X
X    /* The end of a stupid repeat has a finalize_jump back to the
X           start, where another failure point will be made which will
X           point to after all the repetitions found so far.  */
X
X        /* Take off failure points put on by matching on_failure_jump
X           because didn't fail.  Also remove the register information
X           put on by the on_failure_jump.  */
X        case finalize_jump:
X          POP_FAILURE_POINT ();
X        /* Note fall through.  */
X
X    /* Jump without taking off any failure points.  */
X        case jump:
X    nofinalize:
X      EXTRACT_NUMBER_AND_INCR (mcnt, p);
X      p += mcnt;
X      break;
X
X        case dummy_failure_jump:
X          /* Normally, the on_failure_jump pushes a failure point, which
X             then gets popped at finalize_jump.  We will end up at
X             finalize_jump, also, and with a pattern of, say, `a+', we
X             are skipping over the on_failure_jump, so we have to push
X             something meaningless for finalize_jump to pop.  */
X          PUSH_FAILURE_POINT (0, 0);
X          goto nofinalize;
X
X
X        /* Have to succeed matching what follows at least n times.  Then
X          just handle like an on_failure_jump.  */
X        case succeed_n:
X          EXTRACT_NUMBER (mcnt, p + 2);
X          /* Originally, this is how many times we HAVE to succeed.  */
X          if (mcnt)
X            {
X               mcnt--;
X           p += 2;
X               STORE_NUMBER_AND_INCR (p, mcnt);
X            }
X      else if (mcnt == 0)
X            {
X          p[2] = unused;
X              p[3] = unused;
X              goto on_failure;
X            }
X          else
X        {
X              fprintf (stderr, "regex: the succeed_n's n is not set.\n");
X              exit (1);
X        }
X          break;
X
X        case jump_n:
X          EXTRACT_NUMBER (mcnt, p + 2);
X          /* Originally, this is how many times we CAN jump.  */
X          if (mcnt)
X            {
X               mcnt--;
X               STORE_NUMBER(p + 2, mcnt);
X           goto nofinalize;         /* Do the jump without taking off
X                            any failure points.  */
X            }
X          /* If don't have to jump any more, skip over the rest of command.  */
X      else
X        p += 4;
X          break;
X
X    case set_number_at:
X      {
X          register unsigned char *p1;
X
X            EXTRACT_NUMBER_AND_INCR (mcnt, p);
X            p1 = p + mcnt;
X            EXTRACT_NUMBER_AND_INCR (mcnt, p);
X        STORE_NUMBER (p1, mcnt);
X            break;
X          }
X
X        /* Ignore these.  Used to ignore the n of succeed_n's which
X           currently have n == 0.  */
X        case unused:
X          break;
X
X        case wordbound:
X      if (AT_WORD_BOUNDARY)
X        break;
X      goto fail;
X
X    case notwordbound:
X      if (AT_WORD_BOUNDARY)
X        goto fail;
X      break;
X
X    case wordbeg:
X      if (IS_A_LETTER (d) && (!IS_A_LETTER (d - 1) || AT_STRINGS_BEG))
X        break;
X      goto fail;
X
X    case wordend:
X          /* Have to check if AT_STRINGS_BEG before looking at d - 1.  */
X      if (!AT_STRINGS_BEG && IS_A_LETTER (d - 1)
X              && (!IS_A_LETTER (d) || AT_STRINGS_END))
X        break;
X      goto fail;
X
X#ifdef emacs
X    case before_dot:
X      if (PTR_CHAR_POS (d) >= point)
X        goto fail;
X      break;
X
X    case at_dot:
X      if (PTR_CHAR_POS (d) != point)
X        goto fail;
X      break;
X
X    case after_dot:
X      if (PTR_CHAR_POS (d) <= point)
X        goto fail;
X      break;
X
X    case wordchar:
X      mcnt = (int) Sword;
X      goto matchsyntax;
X
X    case syntaxspec:
X      mcnt = *p++;
X    matchsyntax:
X      PREFETCH;
X      if (SYNTAX (*d++) != (enum syntaxcode) mcnt) goto fail;
X          SET_REGS_MATCHED;
X      break;
X
X    case notwordchar:
X      mcnt = (int) Sword;
X      goto matchnotsyntax;
X
X    case notsyntaxspec:
X      mcnt = *p++;
X    matchnotsyntax:
X      PREFETCH;
X      if (SYNTAX (*d++) == (enum syntaxcode) mcnt) goto fail;
X      SET_REGS_MATCHED;
X          break;
X
X#else /* not emacs */
X
X    case wordchar:
X      PREFETCH;
X          if (!IS_A_LETTER (d))
X            goto fail;
X      SET_REGS_MATCHED;
X      break;
X
X    case notwordchar:
X      PREFETCH;
X      if (IS_A_LETTER (d))
X            goto fail;
X          SET_REGS_MATCHED;
X      break;
X
X#endif /* not emacs */
X
X    case begbuf:
X          if (AT_STRINGS_BEG)
X            break;
X          goto fail;
X
X        case endbuf:
X      if (AT_STRINGS_END)
X        break;
X      goto fail;
X
X    case exactn:
X      /* Match the next few pattern characters exactly.
X         mcnt is how many characters to match.  */
X      mcnt = *p++;
X      /* This is written out as an if-else so we don't waste time
X             testing `translate' inside the loop.  */
X          if (translate)
X        {
X          do
X        {
X          PREFETCH;
X          if (translate[*d++] != *p++) goto fail;
X        }
X          while (--mcnt);
X        }
X      else
X        {
X          do
X        {
X          PREFETCH;
X          if (*d++ != *p++) goto fail;
X        }
X          while (--mcnt);
X        }
X      SET_REGS_MATCHED;
X          break;
X    }
X      continue;  /* Successfully executed one pattern command; keep going.  */
X
X    /* Jump here if any matching operation fails. */
X    fail:
X      if (stackp != stackb)
X    /* A restart point is known.  Restart there and pop it. */
X    {
X          short last_used_reg, this_reg;
X
X          /* If this failure point is from a dummy_failure_point, just
X             skip it.  */
X      if (!stackp[-2])
X            {
X              POP_FAILURE_POINT ();
X              goto fail;
X            }
X
X          d = *--stackp;
X      p = *--stackp;
X          if (d >= string1 && d <= end1)
X        dend = end_match_1;
X          /* Restore register info.  */
X          last_used_reg = (short) *--stackp;
X
X          /* Make the ones that weren't saved -1 or 0 again.  */
X          for (this_reg = RE_NREGS - 1; this_reg > last_used_reg; this_reg--)
X            {
X              regend[this_reg] = (unsigned char *) -1;
X              regstart[this_reg] = (unsigned char *) -1;
X              IS_ACTIVE (reg_info[this_reg]) = 0;
X              MATCHED_SOMETHING (reg_info[this_reg]) = 0;
X            }
X
X          /* And restore the rest from the stack.  */
X          for ( ; this_reg > 0; this_reg--)
X            {
X              reg_info[this_reg] = *(struct register_info *) *--stackp;
X              regend[this_reg] = *--stackp;
X              regstart[this_reg] = *--stackp;
X            }
X    }
X      else
X        break;   /* Matching at this starting point really fails.  */
X    }
X
X  if (best_regs_set)
X    goto restore_best_regs;
X  return -1;                     /* Failure to match.  */
X}
X
X
Xstatic int
Xbcmp_translate (s1, s2, len, translate)
X     unsigned char *s1, *s2;
X     register int len;
X     unsigned char *translate;
X{
X  register unsigned char *p1 = s1, *p2 = s2;
X  while (len)
X    {
X      if (translate [*p1++] != translate [*p2++]) return 1;
X      len--;
X    }
X  return 0;
X}
X
X
X
X/* Entry points compatible with 4.2 BSD regex library.  */
X
X#ifndef emacs
X
Xstatic struct re_pattern_buffer re_comp_buf;
X
Xchar *
Xre_comp (s)
X     char *s;
X{
X  if (!s)
X    {
X      if (!re_comp_buf.buffer)
X    return "No previous regular expression";
X      return 0;
X    }
X
X  if (!re_comp_buf.buffer)
X    {
X      if (!(re_comp_buf.buffer = (char *) malloc (200)))
X    return "Memory exhausted";
X      re_comp_buf.allocated = 200;
X      if (!(re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH)))
X    return "Memory exhausted";
X    }
X  return re_compile_pattern (s, strlen (s), &re_comp_buf);
X}
X
Xint
Xre_exec (s)
X     char *s;
X{
X  int len = strlen (s);
X  return 0 <= re_search (&re_comp_buf, s, len, 0, len,
X             (struct re_registers *) 0);
X}
X#endif /* not emacs */
X
X
X
X#ifdef test
X
X#include <stdio.h>
X
X/* Indexed by a character, gives the upper case equivalent of the
X   character.  */
X
Xchar upcase[0400] =
X  { 000, 001, 002, 003, 004, 005, 006, 007,
X    010, 011, 012, 013, 014, 015, 016, 017,
X    020, 021, 022, 023, 024, 025, 026, 027,
X    030, 031, 032, 033, 034, 035, 036, 037,
X    040, 041, 042, 043, 044, 045, 046, 047,
X    050, 051, 052, 053, 054, 055, 056, 057,
X    060, 061, 062, 063, 064, 065, 066, 067,
X    070, 071, 072, 073, 074, 075, 076, 077,
X    0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
X    0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
X    0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
X    0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137,
X    0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
X    0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
X    0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
X    0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177,
X    0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207,
X    0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217,
X    0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227,
X    0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237,
X    0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247,
X    0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257,
X    0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267,
X    0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277,
X    0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307,
X    0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317,
X    0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327,
X    0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337,
X    0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347,
X    0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357,
X    0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367,
X    0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377
X  };
X
X#ifdef canned
X
X#include "tests.h"
X
Xtypedef enum { extended_test, basic_test } test_type;
X
X/* Use this to run the tests we've thought of.  */
X
Xvoid
Xmain ()
X{
X  test_type t = extended_test;
X
X  if (t == basic_test)
X    {
X      printf ("Running basic tests:\n\n");
X      test_posix_basic ();
X    }
X  else if (t == extended_test)
X    {
X      printf ("Running extended tests:\n\n");
X      test_posix_extended ();
X    }
X}
X
X#else /* not canned */
X
X/* Use this to run interactive tests.  */
X
Xvoid
Xmain (argc, argv)
X     int argc;
X     char **argv;
X{
X  char pat[80];
X  struct re_pattern_buffer buf;
X  int i;
X  char c;
X  char fastmap[(1 << BYTEWIDTH)];
X
X  /* Allow a command argument to specify the style of syntax.  */
X  if (argc > 1)
X    obscure_syntax = atoi (argv[1]);
X
X  buf.allocated = 40;
X  buf.buffer = (char *) malloc (buf.allocated);
X  buf.fastmap = fastmap;
X  buf.translate = upcase;
X
X  while (1)
X    {
X      gets (pat);
X
X      if (*pat)
X    {
X          re_compile_pattern (pat, strlen(pat), &buf);
X
X      for (i = 0; i < buf.used; i++)
X        printchar (buf.buffer[i]);
X
X      putchar ('\n');
X
X      printf ("%d allocated, %d used.\n", buf.allocated, buf.used);
X
X      re_compile_fastmap (&buf);
X      printf ("Allowed by fastmap: ");
X      for (i = 0; i < (1 << BYTEWIDTH); i++)
X        if (fastmap[i]) printchar (i);
X      putchar ('\n');
X    }
X
X      gets (pat);    /* Now read the string to match against */
X
X      i = re_match (&buf, pat, strlen (pat), 0, 0);
X      printf ("Match value %d.\n", i);
X    }
X}
X
X#endif
X
X
X#ifdef NOTDEF
Xprint_buf (bufp)
X     struct re_pattern_buffer *bufp;
X{
X  int i;
X
X  printf ("buf is :\n----------------\n");
X  for (i = 0; i < bufp->used; i++)
X    printchar (bufp->buffer[i]);
X
X  printf ("\n%d allocated, %d used.\n", bufp->allocated, bufp->used);
X
X  printf ("Allowed by fastmap: ");
X  for (i = 0; i < (1 << BYTEWIDTH); i++)
X    if (bufp->fastmap[i])
X      printchar (i);
X  printf ("\nAllowed by translate: ");
X  if (bufp->translate)
X    for (i = 0; i < (1 << BYTEWIDTH); i++)
X      if (bufp->translate[i])
X    printchar (i);
X  printf ("\nfastmap is%s accurate\n", bufp->fastmap_accurate ? "" : "n't");
X  printf ("can %s be null\n----------", bufp->can_be_null ? "" : "not");
X}
X#endif /* NOTDEF */
X
Xprintchar (c)
X     char c;
X{
X  if (c < 040 || c >= 0177)
X    {
X      putchar ('\\');
X      putchar (((c >> 6) & 3) + '0');
X      putchar (((c >> 3) & 7) + '0');
X      putchar ((c & 7) + '0');
X    }
X  else
X    putchar (c);
X}
X
Xerror (string)
X     char *string;
X{
X  puts (string);
X  exit (1);
X}
X#endif /* test */
END_OF_FILE
if test 37881 -ne `wc -c <'regex.c2'`; then
    echo shar: \"'regex.c2'\" unpacked with wrong size!
fi
# end of 'regex.c2'
fi
if test -r regex.c1 -a -r regex.c2
then
    echo shar: concatenating \"regex.c1\" and \"regex.c2\" into \"regex.c\"
    cat regex.c1 regex.c2 >regex.c || echo shar: \"regex.c\" creation failed!
fi
echo shar: End of archive 6 \(of 8\).
cp /dev/null ark6isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 8 archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0

exit 0 # Just in case...